---
id: 5900f5241000cf542c510036
title: 'Завдання 437: примітивні корені Фібоначчі'
challengeType: 1
forumTopicId: 302108
dashedName: problem-437-fibonacci-primitive-roots
---

# --description--

Якщо вичислити $8^n$ mod 11 для n від 0 до 9, то отримаємо 1, 8, 9, 6, 4, 10, 3, 2, 5, 7.

Як бачимо, ми отримали всі можливі значення від 1 до 10. Отже, 8 є примітивним коренем 11.

Проте це не все:

Якщо розглянути детальніше, то:

$$\begin{align}   & 1 + 8 = 9 \\\\
  & 8 + 9 = 17 ≡ 6\bmod 11 \\\\   & 9 + 6 = 15 ≡ 4\bmod 11 \\\\
  & 6 + 4 = 10 \\\\   & 4 + 10 = 14 ≡ 3\bmod 11 \\\\
  & 10 + 3 = 13 ≡ 2\bmod 11 \\\\   & 3 + 2 = 5 \\\\
  & 2 + 5 = 7 \\\\ & 5 + 7 = 12 ≡ 1\bmod 11. \end{align}$$

Отже, степені 8 mod 11 циклічні з періодом 10, а $8^n + 8^{n + 1} ≡ 8^{n + 2} (\text{mod } 11)$. Число 8 називають примітивним коренем Фібоначчі за модулем 11.

Не кожне просте число має примітивний корінь Фібоначчі. Існує 323 простих чисел (менших за 10000) з одним чи більше примітивними коренями Фібоначчі, а сума цих простих чисел дорівнює 1480491.

Знайдіть суму простих чисел (менших за $100\\,000\\,000$) з принаймні одним примітивним коренем Фібоначчі.

# --hints--

`fibonacciPrimitiveRoots()` має повернути `74204709657207`.

```js
assert.strictEqual(fibonacciPrimitiveRoots(), 74204709657207);
```

# --seed--

## --seed-contents--

```js
function fibonacciPrimitiveRoots() {

  return true;
}

fibonacciPrimitiveRoots();
```

# --solutions--

```js
// solution required
```
